题目描述
作为新一轮广告大战的一部分，格丁尼亚的一家大公司准备在城市的某处设置公司的标志（logo）。公司经理决定用一些整栋的建筑来构成标志的组成部分。
标志由不同高度的竖直条纹组成。这些条纹从左到右依次编号为 $1\dots n$ . 标志用数字 $1,2,\dots,n$ 的排列 $(s_1,s_2,\dots,s_n)$ 来描述。编号 $s_1$ 的条纹高度最低，编号 $s_2$ 的条纹第二低，……，编号 $s_n$ 的条纹最高。条纹的实际高度无关紧要。
沿格丁尼亚城市的主干道共有 $m$ 栋建筑，这些建筑的高度各不相同。问题是如何找出标志与建筑相匹配的所有位置。
请帮助公司找出匹配标志的建筑序列的连续部分。若编号 $s_1$ 的建筑在序列中最低，编号 $s_2$ 的建筑在序列中第二低，……，那么这个连续的建筑序列就与标志匹配。例如，建筑高度的序列 $5,10,4$ 与用编号排列 $(3,1,2)$ 描述的标志相匹配，因为编号 $3$ 的建筑(高度 $4$ )最低，编号 $1$ 的建筑第二低，编号 $2$ 的建筑最高
输入
第一行包含两个整数 $n,m\quad(2≤n≤m≤1000000)$ .
第二行包含 $n$ 个整数 $s_i$ , 构成 $1,2,\dots,n$ 的排列，$1≤si≤n$ 且 $si≠sj$ .
第三行包含 $m$ 个整数 $h_i$ , 表示建筑的高度 $(1≤hi≤10^9,1≤i≤m)$ ，所有的 $h_i$ 均不相同。
每一行的整数之间用单个空格隔开。
至少 $35$ 分的数据，$n≤5000, m≤2000$
至少 $60$ 分的数据，$n≤50000, m≤200000$
输出
第一行包含 $1$ 个整数 $k$ , 表示匹配的序列数目。
第二行包含 $k$ 个整数，分别为在正确匹配的每个序列中与标志编号 $1$ 的条纹相对应的第 $1$ 栋建筑的编号。这些数字按升序排列，用空格隔开。如果 $k=0$ , 第二行为空行。
样例输入
5 10
2 1 5 3 4
5 6 3 8 12 7 1 10 11 9
样例输出
2
2 6
样例解释
$6,3,8,12,7$ 和 $7,1,10,11,9$ 都与用排列 $(2,1,5,3,4)$ 描述的 logo 相符。
题解
这个问题描述了一个字符串匹配的变种问题。给定两个串：模式串 $P$ 和文本串 $T$ 。任务是找出所有的位置 $j,1 <= j \leq m - n + 1$, 使得模式串在位置 $j$ 匹配文本串。并且，在这个问题中，模式串和文本串都是互异整数列。
模式串 $P$ 不是直接给出来的。输入给出了一个数列 $s$ 来描述 $P$ ：$s_1$ 是 $p$ 中最小的元素，$s_2$ 是第二小的……任意一个等于输入的 $p$ 都是等价的，所以我们假定 $p$ 是 $1..n$ 的一个排列。这种表示很容易由 $s$ 在 $O(n)$ 的时间复杂度内计算出来。
在大部分模式串匹配问题中，模式串与母串在位置 $j$ 匹配当且仅当 $P=T[j\dots j+n-1]$ 。这个问题给出了一种不同的串匹配定义，模式串与母串匹配，当且仅当 $P$ 与 $T[j\dots j+n-1]$ 是同构的。我们称呼两个长度为 $k$ 的串同构，当且仅当 $a[i] < a[j] \Leftrightarrow b[i] < b[j] , \forall 1 \leq i, j \leq k$ 。
为简化符号，我们把 $a$ 与 $b$ 同构写成 $a\sim b$ 。下面，我们有两个简单但是重要的结论。给定三个长为 $k$ 的序列 $a,b,c$.
- 如果 $a\sim b$，则 $a[l\dots r] \sim b[l\dots r],1\leq l \leq r \leq k$.
- 如果 $a \sim b$ 且 $b \sim c$ ，则 $a \sim c$.
为了解决这个问题，我们拓展了 KMP 算法来满足需求。接下来，我们假定读者熟悉 KMP 算法。
计算 fail 指针
我们定义：一个序列 $a[1\dots k]$ 的边界为其一个长为 $t$ 且与 $a[1\dots t]$ 相似的后缀。在 KMP 算法中，我们一开始要计算失败指针 f 。对于每个 $1 \leq i \leq n$，我们想知道串 $P[1\dots i]$ 除自己本身外的最长边界是什么：
$$
f[i] = \max\limits_{k=1}^i p[1..k] \sim p[i - k + 1\dots i]
$$
另外，我们令 $f[0]$ 设为 $0$.
我们以 $i$ 递增的顺序来计算 $f[i]$. $P[1\dots i]$ 的最长边界包括 $P[1\dots i - 1]$ 的一部分和字母 $P[i]$ . 我们遍历 $P[1\dots i - 1]$ 的所有边界，从最长的开始，对于每个边界，我们检查添加一个字母 $P[i]$ 后能否构成 $P[1\dots i]$ 的一个边界。
我们用下面的引理来遍历所有边界，它的证明稍后给出。
引理1
$P[1\dots i]$ 的所有边界的长度依次为 $f[i], f[f[i]], f[f[f[i]]], f[f[f[f[i]]]]\dots$
注意：由于 $0 \leq f[i] < i$ , 上述序列从某些点开始就只出现 $0$ 了。
现在仍然遗留一个问题：如何判断 $P[1\dots i - 1]$ 的一个边界加上一个字母 $P[i]$ 后可以构成 $P[1\dots i]$ 的一个边界。换句话说，给定两个串 $a[1\dots k],b[1\dots k]$（前者是模式串的一个前缀，后者是模式串的一个子串），已知 $a[1\dots k - 1] \sim b[1\dots k - 1]$，如何判断 $a[1\dots k] \sim b[1\dots k]$ . 注意到这就是判断下式是否成立：
$$
a[q] < a[k] \Leftrightarrow b[q] < b[k], \forall 1 \leq q < k
$$
这可以按照下面这个方式重新表述（注意每个序列a、b的元素都是不同的）：
性质1：对于一些 $1\leq r \leq k$ , $a[k]$ 是 $a[1\dots k]$ 中第 $r$ 大的元素，$b[k]$ 是 $b[1\dots k]$ 中第 $r$ 大的元素。
我们现在描述一个检查是否满足上述条件的方法。
设 $a[u]$ 是 $a[1\dots k - 1]$ 中比 $a[k]$ 小的元素中最大的一个，$a[w]$ 是 $a[1\dots k - 1]$ 中比 $a[k]$ 大的元素中最小的一个。我们假定这些元素存在，其他情况类似。根据定义，$a[u] < a[k] < a[w]$ . 我们可以知道判断 $b[u] < b[k] < b[w]$ 是否成立是与判断性质 1 等价的。这是因为 $a[1\dots k - 1] \sim b[1\dots k - 1]$ , 所以 $a[1..k - 1]$ 中比 $a[u]$ 小的数的个数等于 $b[1\dots k - 1]$ 中比 $b[u]$ 小的数的个数。类似地，$a[1..k - 1]$ 中比 $a[w]$ 大的数的个数等于 $b[1..k - 1]$ 中比 $b[w]$ 大的数的个数。所以，这个检测与*性质 1 *实质上是等价的。
现在，我们讨论如何计算 $u$ 和 $w$ 的下标。对于每个 $1 \leq i \leq n$ , 我们需要在 $P[1\dots i]$ 找到比 $P[i]$ 小的最大元素，把这个下标记作 $g[i]$ . 我们也需要知道比 $P[i]$ 大的最小元素，记作 $h[i]$ .（这是一个对称的问题）
注意到 $P[1\dots n]$ 是一个长度为 $n$ 的排列。我们维护一个由 $P[1\dots i]$ 的所有元素构成的递增的双向链表。初始时他只是一个 $1\dots n$ 的所有元素构成的链表。每一步都要删除一个元素。我们记录链表中的每个元素在 $P[1\dots n]$ 中的位置，也记录 $P[1\dots n]$ 的每个元素在链表中的位置。链表使得我们对于每个 $i$ ，可以在常数时间内获得与 $p[i]$ 最接近的元素——他们只是链表中，删除了 $n - i$ 个元素之后，$P[i]$ 的前驱与后继。
这就给出了一个计算 fail 指针的算法。$O(n)$ 预处理出数组 $g[i\dots n]$ 与它的对称问题 $h[i\dots n]$ 之后，算法就与 KMP 算法的失败指针的计算完全一致了。整个算法的运行时间为 $O(n)$ .
寻找匹配
变形的 KMP 匹配算法的主要过程大概如下：
给定模式串的一部分，尽量拓展一个字符。如果不可行，用失败指针得到一个稍短的部分匹配，继续匹配文字。
这也是我们在这个问题中要做的事。用上面的方法，我们能够在常数时间内判断一个部分匹配能不能再拓展一个字符。正确性的证明很简单，主要思想是：如果我们跳过一些正确的匹配（即，我们用失败指针把部分匹配移动得太多超过了匹配的开始），我们马上就得到这与失败指针的定义是矛盾的。
最后，由于匹配过程只是 KMP 算法的轻微修改，所以在 $O(n+m)$ 的时间内可以出解。所以，整个算法只需要线性时间。
附
引理1的证明：
我们证明，如果 $p[1\dots i]$ 有一个长度为 $t$ 的边界，那么比 $t$ 短的最长的边界长度为 $f[t]$ . 如果 $f[t] = 0$ ，那么长度为 $t$ 的边界是最短的一个。从边界的定义可以知道， $p[1..t] \sim p[i - t + 1..i]$ .
我们首先证明 $P[1\dots i]$ 有一个长度为 $f[t]$ 的边界。首先，注意到 $P[1\dots t] \sim P[i - t + 1\dots i]$ . 由此得出，对于每个 $1 \leq s < t$ , $P[1\dots t]$ 有一个长度为s的边界。此外，任意一个 $P[1\dots t]$ 的边界与 $P[i - t + 1\dots i]$ 的边界相似。所以，一个长度为 $f[t]$ 的 $P[1\dots t]$ 的边界与长为 $f[t]$ 的 $P[i - t + 1\dots i]$ 的边界相似。这就表明 $P[1\dots f[t]] \sim P[i - f[t] + 1\dots i]$ .
为了完成这个证明，我们得证明没有长度严格在 $f[t]$ 与 $t$ 之间的边界存在。为了证明这个，我们证明每一个这样长度的边界一定也是 $P[1\dots t]$ 的边界，否则会和 $f[t]$ 的定义相矛盾。设 $f[t] < u < t$ 且 $P[1\dots u] \sim P[i - u + 1\dots i]$ , 也就是说， $P[1\dots i]$ 有一个长度为 $u$ 的边界。这意味着 $P[1\dots t]$ 的一个长度为 $u$ 的后缀与 $P[1..t + 1..t]$ 的一个长度为u的后缀相似。我们已经知道 $P[1..t]$ 和 $P[i - t + 1..i]$ 相似，所以 $P[i - t + 1..i]$ 的一个长为 $u$ 的后缀与 $P[1..i]$ 的一个长为 $u$ 的后缀相似。所以 $P[1\dots t]$的一个长为 $u$ 的后缀与 $P[1\dots u]$ 相似，矛盾。